<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>C++ Tutorial: Binary Tree</title>
  <meta
 content="C++ Tutorial: Binary Tree, Source Code"
 name="description" />
  <meta
 content="C++ Tutorial, Binary Tree, SubTree, In Order print,
 Pre Order print, Post Oder print, Paths from the root to leaves, Successor/Predecessor, Lowest Common Ancestor, Breadth First"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right">
<a href="../gif.html">Gif</a> 
|<a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
| <a href="../OnHTML5.html">HTML5</a>
| <a href="../Algorithms/algorithms.html">Algorithms</a>
| <a href="../News/NewsMain.html">News</a>
| <a href="../cplusplus/cpptut.html">C++</a>
| <a href="../Java/tutorial/on_java.html">Java</a>
| <a href="../php/phptut.html">PHP</a>
| <a href="../DesignPatterns/introduction.html">Design Patterns</a>
| <a href="../python/pytut.html">Python</a> 
| <a href="../CSharp/.netframework.html">C#</a>
| <a href="../forums.html">Forums</a> 
| <a href="../VisualBasicSQL/introduction.html">Visual Basic</a>
</div>
</div>

<div id="contenttext">

<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>

<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>

<br />
<div style="padding: 10px;"><span class="titletext">C++ Tutorial <br />
- Binary Tree Code Example</span></div>
<img src="../images/cplusplus/cpp_logo.jpg" alt="cplusplus logo"/>

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>   
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>
</ul>
</div>
<br />
<br />
<img src="images/binarytree/SoonChunMan.png" alt="SoonChunMan"/>
<br />
<br />
<br />


<div class="bodytext" style="padding: 12px;" align="justify">
<div class="subtitle" id="binarytreeexamples">Binary Tree Example Code</div>
<p>A <strong>binary tree</strong> is made of nodes, where each node contains a <strong>left</strong> pointer, a <strong>right</strong> pointer, and a <strong>data element</strong>. The <strong>root</strong> pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller <strong>subtrees</strong> on either side. A null pointer represents a binary tree with no elements -- the empty tree.</p>
<p>The formal recursive definition is: a <strong>binary tree</strong> is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a <strong>binary tree</strong>. </p>
<p>A <strong>binary search tree (BST)</strong> or <strong>ordered binary tree</strong> is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (&gt;). </p>
<p>Basically, binary search trees are fast at insert and lookup. On average, a binary search tree algorithm can locate a node in an N node tree in order <strong><i>log(n)</i></strong> time (log base 2). Therefore, binary search trees are good for <strong>dictionary</strong> problems where the code inserts and looks up information indexed by some key. The <strong><i>log(n)</i></strong> behavior is the average case -- it's possible for a particular tree to be much slower depending on its shape.</p>
<p>The last tree out of major kinds of trees is a <strong>heap</strong>. A heap is a tree in which each node's children have values less than or equal to node's value. Consequently, the root node always has the largest value in the tree, which means that it's possible to find the maximum value in constant time: Simply return the root value. So, if extraction the max value needs to be fast, we should use a heap.</p>


<br /><br />
<img src="images/binarytree/binarytree_pic.png" alt="binarytree_pic"/>
<br />
<br />
<p>The following items are included in this Binary Search Tree example code. <br />
It's based on the tree in the picture above.</p>
<ul>
	<li><strong>Look Up (lookUp())</strong><br />
	One advantage of a binary search tree is that the lookup operation is fast and simple. This is particularly useful for data storage. This look up is a fast operation because we eliminate half the nodes from our search on each iteration by choosing to follow the left subtree or the right subtree. It is an O<i>(log(n))</i> operation.
	</li>
	<br />
	<li><strong>New Node (newTreeNode())</strong> <br />
	Makes the <strong>root</strong> node.
	</li>
	<br />
	<li><strong>Insert Node (insertTreeNode())</strong><br />
	Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.<br />

	O<i>(log(n))</i> operation
	</li>
	<br />
	<li><strong>Is The Given Tree BST? (isBST())</strong><br />
      The code <strong>isBST()</strong> is the answer to the question: <br />
      Given a binary tree, programmatically you need to prove it is a binary search tree.<br />
If the given binary tree is a binary search tree,then the inorder traversal should output the elements in increasing order. <br />
We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.
	</li>
	<br />
	<li><strong>Size (treeSize())</strong> <br />
	Size of a binary tree is the total number of nodes in the tree. 
	</li>
	<br />
	<li><strong>Maximum/Minimum Depth (maxDepth()/minDepth())</strong> <br />
	The number of nodes along the longest/shortest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0.
	</li>
	<br />
	<li><strong>Is balanced? (isBalanced()) </strong> <br />
	A balanced binary tree is commonly defined as a binary tree in which the height of the two subtrees of every node never differ by more than 1.<br />

	In this example, I used maxDepth(node)-minDepth(node) <= 1
	</li>
	<br />
	<li><strong>Minimum/Maximum Value (maxTree()/ minTree())</strong></li>
	<br />
	<li><strong>In Order Successor/Predecessor (succesorInOrder()/predecessorInOrder()) </strong> <br />
	A node which has the next higher/lower key. 
	</li>
	<br />
	<li><strong>Lowest Common Ancestor (lowestCommonAncestor())</strong></li> 
	<br />
	<li><strong>Clear (Delete Node) </strong> <br />
	O<i>(log(n))</i> operation
	</li>
	<br />
<br />
<img src="images/binarytree/pre_post_in_order.png" alt="pre_post_in_order"/>
<br />
      <li><strong>In Order print (printTreeInOrder())</strong><br />
	Inorder traversal performs the operation first on the node's <strong>left</strong> descendants, then on the <strong>node</strong> itself, and finally on its <strong>right</strong> descendants. In other words, the left subtree is visited first, then the node itself, and then the node's right subtree.
	</li>
	<br />
	<li><strong>Pre Order print (printTreePreOrder())</strong><br />
	Preorder traversal involves walking around the tree in a counterclockwise manner starting at the root. Sticking close to the edge, and printing out the nodes as we encounter them. For the tree shown above, the result is F B A D C E G I H. <br />
	Traversal operation performed first on the <strong>node itself</strong>, then on its <strong>left  descendants</strong>, and finally on its <strong>right descendants</strong>. In other words, a node is always visited before any of its children.
	</li>
	<br />
	<li><strong>Post Oder print (printTreePostOrder())</strong><br />
	Postorder traversal performs the operation first on the node's <strong>left</strong> descendants, then on the node's <strong>right</strong> descendants, and finally on the <strong>node</strong> itself. In other words, all of a node's children are visited before the node itself.
	</li>
	<li><strong>Converting Binary Search Tree into an Array (TreeToArray())</strong> <br />
	How do you put a Binary Search Tree in an array in an efficient manner. <br />
Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise). 
It's not the most efficient way.
	</li>
	<br />
	<li><strong>Paths from the root to leaves (printAllPaths(), pathFinder())</strong> <br />
	Given a binary tree, print out all of its root-to-leaf 
paths, one per line. Uses a recursive helper to do the work. 
	</li>

    	<li><strong>Find n-th maximum node (NthMax()) </strong><br />
	How do you find out the fifth maximum element in a Binary Search Tree in efficient manner. <br />
Note: You should not use any extra space. i.e., sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
	</li>
	
	<br />
	<li><strong>Is Sub Tree? (isSubTree())</strong></li>
	<br />
	<li><strong>Mirror Tree (mirror())</strong> <br />
	Change a tree so that the roles of the left 
and right hand pointers are swapped at every node. </li>
	<br />
	<li><strong>Make a new tree with minimal depth from a sorted array (createMinimalBST(())</strong></li>
	<br />
	<li><strong>Traversing level-order: Breadth-first traversal </strong><br />
	It's nice when we have a tree with ordering properties such as a BST or a heap. Often we're given a tree that isn't BST or a heap. For instance, we may have a tree that is a representation of a family tree or a company job hierarchy. We have to use different techniques to retrieve data from this kind of tree. One common class of problems involves searching for a particular node. There are two very common search algorithms.<br />
		One way to search a tree is to do a <strong>breadth-first search (BFS)</strong>. In a BFS we start with the root, move left to right across the second level, then move left to right across the third level, and so on. We continue the search until either we have examined all of the nodes or we find the node we are searching for. The time to find a node is O(<i>n</i>), so this type of search is best avoided for large trees. A BFS also uses a large amount of memory because it is necessary to track the child nodes for all nodes on a given level while searching that level.<br />
		<strong>BreadthFirstTraversal()</strong> <br />
		</p>
	</li>
    	<li><strong>Depth-First Search</strong> <br />
		Another common way to search for a node is by using a <strong>depth-first search (DFS)</strong>. A depth-first search follows one branch of the tree down as many levels as possible until the target node is found or the end is reached. When the search can't go down any farther, it is continued at the nearest ancestor with unexplored children. DFS has much lower memory requirements than BFS because it is not necessary to store all of the child pointers at each level. In addition, DFS has the advantage that it doesn't examine any single level last (BFS examines the lower level last). This is useful if we suspect that the node we are searching for will be in the lower levels. In this case, a DFS would usually find the target node more quickly than a BFS.<br />
	<strong>InOrder(), PreOrder(), PostOrder()</strong>
	</li>
</li>
</ul>
<br />
<br />
<p>Here is the file for Binary Tree example below: <a href="files/BinaryTree.cpp" target="_blank">BinaryTree.cpp</a>.</p>
<pre>

/* Binary Tree */

#include &lt;iostream&gt;
#include &lt;deque&gt;
#include &lt;climits&gt;
using namespace std;

struct Tree
{
	char data;
	Tree *left;
	Tree *right;  
	Tree *parent;  
};

Tree* lookUp(struct Tree *node, char key)
{
	if(node == NULL) return node;

	if(node->data == key) return node;
	else {
		if(node->data < key)
			return lookUp(node->right, key) ;
		else
			return lookUp(node->left, key);
	}
}

Tree* leftMost(struct Tree *node)
{
	if(node == NULL) return NULL;
	while(node->left != NULL)
		node = node->left;
	return node;
}

struct Tree *newTreeNode(int data) 
{
	Tree *node = new Tree;
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	node->parent = NULL;

	return node;
}

struct Tree* insertTreeNode(struct Tree *node, int data)
{
	static Tree *p;
	Tree *retNode;

	if(node != NULL) p = node;

	if(node == NULL)  {
		retNode = newTreeNode(data);
	    	retNode->parent = p;
		return retNode;
	}
	if(data <= node->data ) { 
		p = node;
		node->left = insertTreeNode(node->left,data);
	} 
	else {
		p = node;
		node->right = insertTreeNode(node->right,data);
	} 
	return node;
}

void isBST(struct Tree *node)
{
	static int lastData = INT_MIN;
	if(node == NULL) return;

	isBST(node->left);

	/* check if the given tree is BST */
	if(lastData < node->data) 
		lastData = node->data;
	else {
		cout << "Not a BST" << endl;
		return;
	}

	isBST(node->right);
	return;
}

int treeSize(struct Tree *node)
{
	if(node == NULL) return 0;
	else
		return treeSize(node->left) + 1 + treeSize(node->right);
}

int maxDepth(struct Tree *node)
{
	if(node == NULL) return 0;

	int leftDepth = maxDepth(node->left);
	int rightDepth = maxDepth(node->right);

	return leftDepth > rightDepth ? 
				leftDepth + 1 : rightDepth + 1;
}

int minDepth(struct Tree *node)
{
	if(node == NULL) return 0;

	int leftDepth = minDepth(node->left);
	int rightDepth = minDepth(node->right);

	return leftDepth < rightDepth ? 
				leftDepth + 1 : rightDepth + 1;
}

bool isBalanced(struct Tree *node)
{
	if(maxDepth(node)-minDepth(node) <= 1) 
		return true;
	else
		return false;
}

/* Tree Minimum */
Tree* minTree(struct Tree *node)
{
	if(node == NULL) return NULL;
	while(node->left) 
		node = node -> left;
	return node;
}

/* Tree Maximum */
Tree* maxTree(struct Tree *node)
{
	while(node->right) 
		node = node -> right;
	return node;
}

/* In Order Successor - a node which has the next higher key */ 
Tree *succesorInOrder(struct Tree *node)
{
	/* if the node has right child, seccessor is Tree-Minimum */
	if(node->right != NULL) return minTree(node->right);

	Tree *y = node->parent;
	while(y != NULL && node == y->right) {
		node = y;
		y = y->parent;
	}
	return y;
}

/* In Order Predecessor - a node which has the next lower key */
Tree *predecessorInOrder(struct Tree *node)
{
	/* if the node has left child, predecessor is Tree-Maximum */
	if(node->left != NULL) return maxTree(node->left);

	Tree *y = node->parent;
	/* if it does not have a left child, 
	predecessor is its first left ancestor */
	while(y != NULL && node == y->left) {
		node = y;
		y = y->parent;
	}
	return y;
}
 
Tree *lowestCommonAncestor(Tree *root, Tree *p, Tree *q) 
{
	Tree *left, *right;
	if(root == NULL) return NULL;
	if(root->left == p || root->left == q
		|| root->right == p || root->right == q) return root;
	else {
		left = lowestCommonAncestor(root->left,p,q);
		right = lowestCommonAncestor(root->right, p,q);
		if(left && right) 
			return root;
		else 
			return (left) ? left : right;
	}	
}

void clear(struct Tree *node)
{
	if(node != NULL) {
		clear(node->left);
		clear(node->right);
		delete node;
	}
}
/* print tree in order */
/* 1. Traverse the left subtree. 
   2. Visit the root. 
   3. Traverse the right subtree. 
*/

void printTreeInOrder(struct Tree *node)
{
	static int lastData = INT_MIN;
	if(node == NULL) return;

	printTreeInOrder(node->left);
	cout << node->data << " ";
	printTreeInOrder(node->right);
}

/* print tree in postorder*/
/* 1. Traverse the left subtree. 
   2. Traverse the right subtree. 
   3. Visit the root. 
*/
void printTreePostOrder(struct Tree *node)
{
	if(node == NULL) return;

	printTreePostOrder(node->left);
	printTreePostOrder(node->right);
	cout << node->data << " ";
}

/* print in preorder */
/* 1. Visit the root. 
   2. Traverse the left subtree. 
   3. Traverse the right subtree. 
*/
void printTreePreOrder(struct Tree *node)
{
	if(node == NULL) return;

	cout << node->data << " ";
	printTreePreOrder(node->left);
	printTreePreOrder(node->right);
}

/* printing array */
void printThisPath(int path[], int n)
{
	for(int i = 0; i < n; i++)
		cout << (char)path[i] << " ";
	cout << endl;
}

/* recursion routine to find path */
void pathFinder(struct Tree *node, int path[], int pathLength)
{
	if(node == NULL) return;
	path[pathLength++] = node->data;

	/* Leaf node is the end of a path. 
	   So, let's print the path */
	if(node->left == NULL && node->right == NULL)
		printThisPath(path, pathLength);
	else {
		pathFinder(node->left, path, pathLength);
		pathFinder(node->right, path, pathLength);
	}
}

/*printing all paths :
Given a binary tree, print out all of its root-to-leaf 
paths, one per line. Uses a recursive helper to do the work. */

void printAllPaths(struct Tree *root)
{
	int path[100];
	pathFinder(root,path,0);
}

bool matchTree(Tree *r1, Tree *r2)
{
	/* Nothing left in the subtree */
	if(r1 == NULL && r2 == NULL)
		return true;
	/* Big tree empty and subtree not found */
	if(r1 == NULL || r2 == NULL)
		return false;
	/* Not matching */
	if(r1->data != r2->data)
		return false;
	return (matchTree(r1->left, r2->left) && 
			matchTree(r1->right, r2->right));
}

bool subTree(Tree *r1, Tree *r2)
{
	/*Big tree empty and subtree not found */
	if(r1 == NULL)
		return false;
	if(r1->data == r2->data)
		if(matchTree(r1, r2)) return true;
	return (subTree(r1->left, r2) || subTree(r1->right, r2));
}

bool isSubTree(Tree *r1, Tree *r2)
{
	/* Empty tree is subtree */
	if(r2 == NULL) 
		return true;
	else
		return subTree(r1, r2);
}

/* change a tree so that the roles of the left 
and right hand pointers are swapped at every node */
void mirror(Tree *r)
{
	if(r == NULL) return;
	
	Tree *tmp;
	mirror(r->left);
	mirror(r->right);

	/* swap pointers */
	tmp = r->right;
	r->right = r->left;
	r->left = tmp;
}

/* create a new tree from a sorted array */
Tree *addToBST(char arr[], int start, int end)
{
	if(end < start) return NULL;
	int mid = (start + end)/2;

	Tree *r = new Tree;
	r->data = arr[mid];
	r->left = addToBST(arr, start, mid-1);
	r->right = addToBST(arr, mid+1, end);
	return r;
}

Tree *createMinimalBST(char arr[], int size)
{
	return addToBST(arr,0,size-1);
}

/* Breadth first traversal using queue */
void BreadthFirstTraversal(Tree *root)
{
	if (root == NULL) return;
	deque &lt;Tree *&gt; queue;
	queue.push_back(root);

	while (!queue.empty()) {
		Tree *p = queue.front();
		cout << p->data << " ";
		queue.pop_front();

		if (p->left != NULL)
			queue.push_back(p->left);
		if (p->right != NULL)
			queue.push_back(p->right);
	}
	cout << endl;
} 

/* find n-th max node from a tree */
void NthMax(struct Tree* t)
{        
	static int n_th_max = 5;
	static int num = 0;
	if(t == NULL) return;        
	NthMax(t->right);        
	num++;        
	if(num == n_th_max)                
		cout << n_th_max << "-th maximum data is " << t->data << endl;        
	NthMax(t->left);
}

/* Converting a BST into an Array */ 
void TreeToArray(struct Tree *node, int a[]){ 
	static int pos = 0; 
  
	if(node){ 
		TreeToArray(node->left,a); 
		a[pos++] = node->data; 
		TreeToArray(node->right,a); 
      } 
} 

int main(int argc, char **argv)
{
	char ch, ch1, ch2;
	Tree *found;
	Tree *succ;
	Tree *pred;
	Tree *ancestor;
	char charArr[9] 
		= {'A','B','C','D','E','F','G','H','I'};

	Tree *root = newTreeNode('F');
	insertTreeNode(root,'B');
	insertTreeNode(root,'A');
	insertTreeNode(root,'D');
	insertTreeNode(root,'C');  
	insertTreeNode(root,'E');
	insertTreeNode(root,'G');
	insertTreeNode(root,'I');
	insertTreeNode(root,'H');

	/* is the tree BST? */
	isBST(root);

	/* size of tree */
	cout << "size = " << treeSize(root) << endl;

	/* max depth */
	cout << "max depth = " << maxDepth(root) << endl;

	/* min depth */
	cout << "min depth = " << minDepth(root) << endl;

	/* balanced tree? */
	if(isBalanced(root))
		cout << "This tree is balanced!\n";
	else
		cout << "This tree is not balanced!\n";

	/* min value of the tree*/
	if(root) 
		cout << "Min value = " << minTree(root)->data << endl;

	/* max value of the tree*/
	if(root) 
		cout << "Max value = " << maxTree(root)->data << endl;

	ch = 'B';
	found = lookUp(root,ch);
	if(found) {
		cout << "Min value of subtree " << ch << " as a root is "
			 << minTree(found)->data << endl;
		cout << "Max value of subtree " << ch << " as a root is "
			 << maxTree(found)->data << endl;
	}

	ch = 'B';
	found = lookUp(root,ch);
	if(found) {
		succ = succesorInOrder(found);
		if(succ)
			cout << "In Order Successor of " << ch << " is "
			 << succesorInOrder(found)->data << endl;
		else 
			cout << "In Order Successor of " << ch << " is None\n";
	}

	ch = 'E';
	found = lookUp(root,ch);
	if(found) {
		succ = succesorInOrder(found);
		if(succ)
			cout << "In Order Successor of " << ch << " is "
			 << succesorInOrder(found)->data << endl;
		else 
			cout << "In Order Successor of " << ch << " is None\n";
	}

	ch = 'I';
	found = lookUp(root,ch);
	if(found) {
		succ = succesorInOrder(found);
		if(succ)
			cout << "In Order Successor of " << ch << " is "
			 << succesorInOrder(found)->data << endl;
		else 
			cout << "In Order Successor of " << ch << " is None\n";
	}

	ch = 'B';
	found = lookUp(root,ch);
	if(found) {
		pred = predecessorInOrder(found);
		if(pred)
			cout << "In Order Predecessor of " << ch << " is "
			 << predecessorInOrder(found)->data << endl;
		else 
			cout << "In Order Predecessor of " << ch << " is None\n";
	}

	ch = 'E';
	found = lookUp(root,ch);
	if(found) {
		pred = predecessorInOrder(found);
		if(pred)
			cout << "In Order Predecessor of " << ch << " is "
			 << predecessorInOrder(found)->data << endl;
		else 
			cout << "In Order Predecessor of " << ch << " is None\n";
	}

	ch = 'I';
	found = lookUp(root,ch);
	if(found) {
		pred = predecessorInOrder(found);
		if(pred)
			cout << "In Order Predecessor of " << ch << " is "
			 << predecessorInOrder(found)->data << endl;
		else 
			cout << "In Order Predecessor of " << ch << " is None\n";
	}

	/* Lowest Common Ancestor */
	ch1 = 'A';
	ch2 = 'C';
	ancestor = 
		lowestCommonAncestor(root, 
			lookUp(root,ch1), lookUp(root,ch2));
	if(ancestor) 
		cout << "The lowest common ancestor of " << ch1 << " and "
		<< ch2 << " is " << ancestor->data << endl;

	ch1 = 'E';
	ch2 = 'H';
	ancestor = 
		lowestCommonAncestor(root, 
			lookUp(root,ch1), lookUp(root,ch2));
	if(ancestor) 
		cout << "The lowest common ancestor of " << ch1 << " and "
		<< ch2 << " is " << ancestor->data << endl;

	/* print tree in order */
	cout << "increasing sort order\n";
	printTreeInOrder(root);
	cout << endl;

	/* print tree in postorder*/
	cout << "post order \n";
	printTreePostOrder(root);
	cout << endl;

	/* print tree in preorder*/
	cout << "pre order \n";
	printTreePreOrder(root);
	cout << endl;

	/* lookUp */
	ch = 'D';
	found = lookUp(root,ch);
	if(found) 
		cout << found->data << " is in the tree\n";
	else
		cout << ch << " is not in the tree\n";

	/* lookUp */
	ch = 'M';
	found = lookUp(root,ch);
	if(found) 
		cout << found->data << " is in the tree\n";
	else
		cout << ch << " is not in the tree\n";

	/* printing all paths :
	Given a binary tree, print out all of its root-to-leaf 
	paths, one per line. Uses a recursive helper to do the work. */
	cout << "printing paths ..." << endl;
	printAllPaths(root); 

	/* find n-th maximum node */
	NthMax(root);


	/* convert the tree into an array */
	int treeSz = treeSize(root);
	int *array = new int[treeSz];
	TreeToArray(root,array);
	cout << "New array: ";
	for (int i = 0; i < treeSz; i++)
		cout << (char)array[i] << ' ';
	cout << endl;
	delete [] array;

	/* subtree */
	Tree *root2 = newTreeNode('D');
	insertTreeNode(root2,'C');  
	insertTreeNode(root2,'E');
	cout << "1-2 subtree: " << isSubTree(root, root2) << endl;

	Tree *root3 = newTreeNode('B');
	insertTreeNode(root3,'A');  
	insertTreeNode(root3,'D');
	insertTreeNode(root3,'C');  
	insertTreeNode(root3,'E');
	cout << "1-3 subtree: " << isSubTree(root, root3) << endl;

	Tree *root4 = newTreeNode('B'); 
	insertTreeNode(root4,'D');
	insertTreeNode(root4,'C');  
	insertTreeNode(root4,'E');
	cout << "1-4 subtree: " << isSubTree(root, root4) << endl;

	cout << "2-3 subtree: " << isSubTree(root2, root3) << endl;
	cout << "3-2 subtree: " << isSubTree(root3, root2) << endl;

	/* swap left and right */
	mirror(root);

	/* deleting a tree */
	clear(root);

	/* make a new tree with minimal depth */
	Tree *newRoot = createMinimalBST(charArr,9);

	/* Traversing level-order. 
	We visit every node on a level before going to a lower level. 
	This is also called Breadth-first traversal.*/
	cout << "printing with Breadth-first traversal" << endl;
	BreadthFirstTraversal(newRoot);

	return 0;
}
</pre>
<p>From the run, we get:</p>
<pre>
size = 9
max depth = 4
min depth = 2
This tree is not balanced!
Min value = A
Max value = I
Min value of subtree B as a root is A
Max value of subtree B as a root is E
In Order Successor of B is C
In Order Successor of E is F
In Order Successor of I is None
In Order Predecessor of B is A
In Order Predecessor of E is D
In Order Predecessor of I is H
The lowest common ancestor of A and C is B
The lowest common ancestor of E and H is F
increasing sort order
A B C D E F G H I
post order
A C E D B H I G F
pre order
F B A D C E G I H
D is in the tree
M is not in the tree
printing paths ...
F B A
F B D C
F B D E
F G I H
5-th maximum data is E
New array: A B C D E F G H I
1-2 subtree: 1
1-3 subtree: 1
1-4 subtree: 0
2-3 subtree: 0
3-2 subtree: 1
printing with Breadth-first traversal
E B G A C F H D I
</pre>

<div id="rightpanel">
<div align="center">
</div></div>

<br /><br />
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a> </li>
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>

</ul>
<br /><br />

<br />


<br />
<br />
<br />


</div>
</div>
<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2011 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a>
</div>
</div>
</div>
</body>
</html>
